import java.util.*;

public class demo1 {

    public static class BinarySearchTree {

        static class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;

            public TreeNode(int val) {
                this.val = val;
            }
        }

        public TreeNode root;

        public boolean search(int key) {
            TreeNode cur = root;
            while (cur != null) {
                if (cur.val < key) {
                    cur = cur.right;
                } else if (cur.val > key) {
                    cur = cur.left;
                } else {
                    return true;
                }
            }
            return false;
        }

        public boolean insert(int val) {
            if (root == null) {
                root = new TreeNode(val);
                return true;
            }
            TreeNode parent = null;
            TreeNode cur = root;
            while (cur != null) {
                parent = cur;
                if (cur.val > val) {
                    cur = cur.left;
                } else if (cur.val < val) {
                    cur = cur.right;
                } else {
                    return false;
                }
            }
            if (parent.val > val) {
                parent.left = new TreeNode(val);
            } else {
                parent.right = new TreeNode(val);
            }
            return true;
        }

        public boolean remove(int key) {
            TreeNode cur = root;
            TreeNode parent = null;
            while (cur != null) {
                parent = cur;
                if (cur.val < key) {
                    cur = cur.right;
                } else if (cur.val > key) {
                    cur = cur.left;
                } else {
                    removeNode(cur, parent);
                    return true;
                }
            }
            return false;
        }

        private void removeNode(TreeNode cur, TreeNode parent) {
            if (cur.left == null) {
                if (cur == root) {
                    root = cur.right;
                } else if (cur == parent.left) {
                    parent.left = cur.right;
                } else if (cur == parent.right) {
                    parent.right = cur.right;
                }
            } else if (cur.right == null) {
                if (cur == root) {
                    root = cur.left;
                } else if (cur == parent.left) {
                    parent.left = cur.left;
                } else if (cur == parent.right) {
                    parent.right = cur.left;
                }
            } else {
                //cur.left!=null && cur.right!=null
                TreeNode targetParent = cur;
                TreeNode target = cur.right;
                while (target.left != null) {
                    targetParent = target;
                    target = target.left;
                }
                cur.val = target.val;
                //删除target
                if (targetParent.left == target) {
                    targetParent.left = target.right;
                } else {
                    targetParent.right = target.right;
                }
            }
        }


    }

    public static class HashBuck {
        static class Node {
            public int key;
            public int val;
            public Node next;

            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }

        public Node[] array;
        public int usedSize; //存储了多少个数据
        public static final float DEFAULT_LOAD_FACTOR = 0.75f;

        public HashBuck() {
            array = new Node[10];
        }

        public void put(int key, int val) {
            int index = key % array.length;

            //遍历index下标的链表，是否存在value，不存在进行头插法插入数据
            Node cur = array[index];
            while (cur != null) {
                if (cur.key == key) {
                    //更新value
                    cur.val = val;
                }
                cur = cur.next;
            }

            //cur == null 链表遍历完了，没有找到key
            Node node = new Node(key, val);
            node.next = array[index];
            array[index] = node;
            usedSize++;

            if (doLoadFactor() > DEFAULT_LOAD_FACTOR) {
                //扩容

            }
        }

        private void resize() {
            Node[] newArray = new Node[2 * array.length];

            //遍历原来的数组
            for (int i = 0; i < array.length; i++) {
                Node cur = array[i];
                //遍历每个链表元素
                while (cur != null) {
                    Node tmp = cur.next;
                    int newIndex = cur.key % newArray.length; //新的数组下标
                    //采用头插法插入到新数组
                    cur.next = newArray[newIndex];
                    newArray[newIndex] = cur;
                    cur = tmp;
                }
            }

            array = newArray;
        }

        private float doLoadFactor() {
            return usedSize * 1.0f / array.length;
        }

        public int get(int key) {
            int index = key % array.length;
            Node cur = array[index];
            while (cur != null) {
                if (cur.key == key) {
                    return cur.val;
                }
                cur = cur.next;
            }
            return -1;
        }
    }

    public static class Test {

        public static void main(String[] args) {
            HashBuck hashBuck = new HashBuck();
            hashBuck.put(1,2);
            hashBuck.put(2,3);
            hashBuck.put(4,5);
            System.out.println(hashBuck.get(4));
        }

        public static void main3(String[] args) {
            Set<String> set = new TreeSet<>();
            set.add("sunny");
            set.add("the");
            set.add("hell0");
            System.out.println(set);
            Iterator<String> it = set.iterator();
            while(it.hasNext()){
                System.out.println(it.next());
            }
        }
        public static void main2(String[] args) {
            Map<String,Integer> map = new TreeMap<>();
            map.put("sunny",3);
            map.put("the",5);
            map.put("hello",2);

            System.out.println(map.get("sunny1"));
            System.out.println(map.getOrDefault("sunny1",99999));
            System.out.println(map.get("the"));

            Set<String> set = map.keySet();
            System.out.println(set);

            Set<Map.Entry<String,Integer>> entrySet = map.entrySet();

            for(Map.Entry<String,Integer> entry:entrySet) {
                System.out.println("key: "+entry.getKey() + " vale: "+entry.getValue());
            }

            Map<String,Integer> map2 = new HashMap<>();


        }


        public static void main1(String[] args) {
            BinarySearchTree binarySearchTree = new BinarySearchTree();
            int[] array = {5,12,3,2,11,15};
            for(int i = 0;i < array.length;i++) {
                binarySearchTree.insert(array[i]);
            }
            binarySearchTree.remove(12);
            System.out.println(binarySearchTree.search(12));
            System.out.println(binarySearchTree.search(2));
            System.out.println(binarySearchTree.search(22));
        }
    }
}
